/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-07 16:49:46
 * @LastEditors: lily
 * @LastEditTime: 2021-04-08 09:51:01
 */
/*
 * @lc app=leetcode.cn id=509 lang=javascript
 *
 * [509] 斐波那契数
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */

//  思路：动态规划+滚动数组
//  复杂度：O(n)  O(1)
var fib = function (n) {
    if (n < 2) {
        return n
    }
    // let dp = new Array(n + 1).fill(0)
    // dp[0] = 0
    // dp[1] = 1
    let res = 1, mid = 0, pre = 0
    for (let i = 2; i < n + 1; i++) {
        pre = mid
        mid = res
        res = mid + pre
    }
    return res
};
// @lc code=end

console.log(fib(50));